<?php
/**
 * @title 802. 找到最终的安全状态 - 递归优化
 * @author start2004
 */

// ini_set("memory_limit", "128M");

// class Solution {
//
//     function find() {
//
//     }
// }

class Solution {

    /**
     * @param Integer[][] $graph
     * @return Integer[]
     */
    function eventualSafeNodes($graph) {
        /**
         * @since 2021-08-05 安全点
         */
        $this->safeArray = [];

        /**
         * @since 2021-08-05 不安全点
         */
        $this->unsafeArray = [];
        $this->graph = $graph;

        /**
         * @since 2021-08-05 节点数量
         */
        $len = count($graph);

        /**
         * @since 2021-08-05 逐个点迭代
         */
        for($i=0; $i<$len; $i++){
            self::find([], $i);
        }

        /**
         * @return
         */
        sort($this->safeArray);
        return $this->safeArray;
    }

    /**
     * @title 查找该点是否存出发的路径, 是否存在闭环
     * @author start2004
     * @since 2021-08-05 Created
     *
     * @param array $arriveArray
     * @param int $node
     */
    public function find($arriveArray = [], $node = 0){
        /**
         * @since 2021-08-05 回到途经点, node是不安全点
         */
        if(isset($arriveArray[$node]) OR isset($this->unsafeArray[$node])){
            /**
             * @since 2021-08-05 所有途经点都是不安全点
             */
            foreach ($arriveArray as $node){
                $this->unsafeArray[$node] = $node;
            }
            return false;
        } else {}

        /**
         * @since 2021-08-05 node是安全点
         */
        if(isset($this->safeArray[$node])){
            return true;
        } else {}

        /**
         * @since 2021-08-05 node出发点, 递归
         */
        $arriveArray[$node] = $node;
        foreach ($this->graph[$node] as $next){
            if(self::find($arriveArray, $next) === false){
                return false;
            } else {}
        }

        /**
         * @return
         */
        $this->safeArray[$node] = $node;
        return true;
    }
}

/**
 * @url http://127.0.0.1/leetcode/202108/2021.08.05_2.php
 */
$datas = [
    [[[1,2],[2,3],[5],[0],[5],[],[]]], // 2,4,5,6
    [[[1,2,3,4],[1,2],[3,4],[0,4],[]]], // 4
    [[[],[0,2,3,4],[3],[4],[]]], // 0,1,2,3,4
    [[[156,390],[78,298,347,488],[395,422,498],[98,395,407,429],[19,386,454],[123,183,275,432,473],[229,276,345,367],[70,286,387],[29,95,96,180,183,491],[28,69,212,402],[],[69,247],[108,163],[408,466,476],[73,128],[48,150,189,485],[],[246,438],[],[63,293,419],[25,231,370,445],[],[267,423,465],[275,477],[],[252],[22,167],[29,142,260,356,383,433],[],[81,179,313],[48],[197],[186,321,325,482],[189,193,273,297,385,434],[77,116,237,333,442],[447],[98,143,258,327],[135,418],[230,270],[272],[],[],[57,97,186,252,289],[142,159,239,240,295],[347],[85,279,293,391,467],[96,145,219,237,297],[61,237,493,495],[80,210,233,236,379,448],[105,213,259,303,395,397],[56,129],[100,295,338,470],[117],[132,285,403,453,477],[215,421],[55,97,119,155,389],[432],[163,252,305,332,389,397],[178,398],[73,143,234,295,369],[],[],[224,293,323,398,419,441],[79,314,394,398],[10,439,468,498],[],[103,104,109,396,489],[196,388],[154,245,334,495],[69,122,157,360,418,461],[217,481],[190,343,382],[150,203,253,388,472],[269],[123,211,261,355],[],[118,209,266,335,385,439],[85,242,477,490],[],[],[],[364,475],[],[244],[171,280],[],[197,296,314],[],[170,282,385],[140,319,438],[228,410],[],[],[177,316,345,372,375,412],[172,215,366,404,424,492],[120,147,166,227,273,435],[100,148,256,446,457,472],[],[327,368],[154,246,352,483],[114,178,357,416],[130,451],[167,281,422,484],[170,191],[192,205,346,355],[219,484],[120,186,268,335,370,459],[174,453],[72,268,283,320,365,468],[223],[184,318,323,425,477,492],[189,216,325,337,344,378],[],[133,187,253,263,330,480],[175,194,227,244,303,351],[169,326,426,432],[377,470],[248],[209,321,359,367,417,426],[295,427,444],[158,268,365],[],[191,331,367,449],[153,207,215,281,370],[57],[195,264],[228],[205,215,270,288,490],[257,280,401,422],[162,217,263,313,447,484],[198,234,402,468,499],[267,276,386,442,443,454],[241,257,345,366,387,462],[],[143,159,202,243,395,470],[218,408,412,482],[170,349,481],[169,192,269,295,335],[148,177,196,314],[184,224,253,398,420,487],[429],[],[193,369,430,491],[171,216,227,378,466],[39,303,417,455,480],[199,282,311,313,323,382],[200],[422,437],[162,218,430,441],[267,276,325,345,480],[154],[],[37],[161,463,496],[228,339,359],[158,217,239,252,256],[236,328,405,497],[208,311,339,481],[165,196,243,415],[],[214,442,457,491],[200,275,290,358,360,367],[304],[285,476],[200,222,288,346,391,421],[196,342,351,433],[178,200,296,352],[407,431,451,470],[211,224,227,302,404],[322,323,370,478],[177,488],[212,404,456,463],[225,296,338,454,487],[],[281],[206,207,359,366,437,488],[185,299,333,365,378,449],[97,340,446,464],[],[58,468],[326],[190,197,206,311,365,407],[],[],[266,273,358,404,453],[254,360,365,476],[388],[323,431],[200,217,270,408,428,470],[238],[315,371],[236,365,403,441,481],[236,373,462],[396],[207,331,378],[239,299,381,424,444,488],[227],[],[285,319,344,422,437],[242,244],[263,276,408],[400,429],[376,422,445,464,468],[],[386,476],[300,367,423],[207,310,321],[232,275,316,329,448],[294,309],[405],[],[228,259,327,381,413],[214,242,363,451,454],[234,286,288,324,339,409],[257,278,406,444,445],[252,354],[384,486],[255,328,457,470],[244,290,320,332,420],[246,303,471,480],[335,341,419,440],[232,262,287,369],[321,430,472,483],[309,425],[316],[307,311,369,467],[251,261,318,374,472,488],[],[347],[285,371,422,482,488],[243,269,345],[438],[399,407],[415],[315,351,378,463],[253,285,288,328,423],[337,378,457],[427],[372,406,432,485],[253,283,308,354,356,437],[261,343,390,393,403,409],[353,468],[],[248,283,373,435,469,493],[251,346,429,430,463,468],[480],[260,352,462,488],[255,472],[134,376,461,499],[],[441,456],[357,430,434,438,450],[],[284,299,307,342,403,436],[314,368,381,439,450],[358,382,471],[],[],[290,384,451,467],[263,316,375,380],[339,436,458,497],[],[362,419,443,474,497],[],[200,318,369,418,464],[448,453,463],[3,452],[327,329,357,409,446,494],[410,454,472],[326,363,383,476],[471],[284,371,446],[350,426],[341,369,459,476],[332,353,367,394,443,449],[1,326,465],[],[280,282,364,370,457,479],[287,342,457,464,484,491],[375,456,488],[296,431,488],[370,432,450,469],[314,389,418,421,431,493],[476],[422],[362,438,449,486],[328,329,348,370],[],[291,365,499],[339,341,424,477,480,491],[305,326,369,486,487],[333,378,429],[],[],[164],[253,359],[467],[314,322,384,432,456,489],[307,364,436,442],[344,382,387,458,481],[371,386,388,421],[430,490],[337,341,354,358,494],[],[373,395],[],[337,377,386,414,471,485],[314,335,402,418,455,475],[335,346,384,440],[],[346,353,430,478],[325,402,457],[321,363,448,463],[],[64,328,370,398,403],[356,368,404],[336,342],[371,438,464],[391],[322,374,436,441],[374],[352,391,398,409,490],[346,353,364,369],[359,395,427],[],[],[360,372,396,428,466,471],[417,419,433,458,460,484],[373,388,413,444,480,498],[330,366,463],[375,393,401,415,454,487],[],[],[420,461],[349,372,413,419,462,469],[410,419,439],[],[363,368,370,424,468],[340,351,363,439,452,492],[415,417,438,475],[342,354,381,457,477],[458,490],[407,420,421,466],[351,354,371,375],[],[349,373],[381,465],[379,420,467],[438],[353,399,415,428,476,495],[390,423,438,462],[387,390,471,481,496],[],[426],[412,422,429,450,455],[374,417,460,479],[433,450],[386,389,403,404,456,475],[381,389,425,460,470,499],[405,414,476],[376,391,454],[413,422,432,443,464,488],[391],[133],[412,431,453,467,482,497],[367,383,428,441,478],[391],[376,469],[386,394,434,445,461],[397,434],[373,422,449,467,483,494],[],[425,436,495],[392,417,446,487],[406,460,493],[448,449],[425,480],[384,460],[389,439,448,456,458,483],[341,384,444,487],[385,404,428,432,468],[398,420,436,445,471],[],[],[422,440],[492],[428,438,453,455],[432],[432],[],[],[403,440,445],[400,418,437,475,478,483],[413,437,480,482],[448,449,456,471,491],[409,442,450,455,460,467],[],[409,422,447,486,489,498],[401,410,424,472,476,496],[424,427,437,472],[462,475,479],[423,441,475],[409,431,456,465,488,490],[331,404,448],[493],[408,409,437,486],[408,442,481,488],[427,442,470],[],[447,458,463,477,483,491],[424,435,445,470,495,496],[434,436],[],[418,452,479,491,497],[460],[431,433,450,485,489],[425,437,440,452,453,496],[19,429,433,439,466,475,491],[420,429,497],[424,478],[175,425,443,481],[428,441,449,469,470,479],[464,493],[429,444,446,453,492],[442,447,451,457,478],[444,450,476,487],[451,454,463,475,486],[486],[434],[431,435,459,478,489,494],[436,438,442,486,496],[456],[445,482,493,495],[449,460,463,495],[],[440,443,460],[446,453,460,475,477,489],[61,483,485,491],[],[456,461],[462,470,480,490],[446,450,464,468,477,489],[469,477,479,481,488,492],[446,489],[458,473],[454,462,464,470,485,498],[476,478],[488,494,496,498,499],[],[498],[484],[463,465,480],[],[458,463,473,483,487,492],[475,481,483,487,489],[467,499],[472,479,480,492,497],[461,474,497,498],[159,469,473,490],[465,468,471,474,487,495],[466,470,477,483],[463,473,475,481,484,491],[464,465,468,472,483,486],[469,473,490,497],[465,466,473,483],[469,478],[468,480,498],[],[478],[472,490],[482,487,493,495,499],[484,488,495],[483,487,490,495],[478,479,481,485,486],[484,497],[479,480,488],[481,482,483,485,487,489],[],[479,494,498],[],[481,485],[489,492,493],[486,499],[486,492,494,499],[486,492,494,499],[491,492,495],[490],[488,492],[494],[494,495],[],[493,497],[493,498],[494,495,496,497,498,499],[495,496,497,499],[496,497,499],[497,498,499],[498,499],[499],[]]], //
];

include_once dirname(__DIR__) . DIRECTORY_SEPARATOR ."xhprof.php";
$xhprof = new Xhprof();
foreach ($datas as $data){
    var_dump($data);

    $obj = new Solution();
    $result = $obj->eventualSafeNodes(...$data);
    // $result = $obj->($xhprof->tree($data));
    // $result = $obj->($xhprof->listNode($data));
    // $result = $obj->find(...$data);
    var_dump($result);
    // if(count($result)<=20){
    //     var_dump($result);
    // } else {
    //     var_dump(count($result));
    // }
    echo str_repeat(PHP_EOL, 3);
    echo str_repeat("<br>", 3);
}

// foreach ($datas as $data){
//     $obj = new $data[0][0](...$data[1][0]);
//
//     for ($i=1; $i<count($data[0]); $i++){
//         $func = $data[0][$i];
//         $param = $data[1][$i];
//         $result = $obj->$func(...$param);
//
//         echo $data[0][$i] ."(\"". implode(",", $data[1][$i]) ."\") ";
//             if($result === true){
//                 echo "True";
//             } elseif($result === false) {
//                 echo "False";
//             } elseif($result === null) {
//                 echo "Null";
//             } elseif(is_array($result)) {
//                 var_dump($result);
//             } else {
//                 echo $result;
//             }
//         echo PHP_EOL;
//     }
//
//     echo str_repeat(PHP_EOL, 3);
// }
$xhprof->end();
